#ifndef __BASE_DEDUP_DOT_HPP__
#define __BASE_DEDUP_DOT_HPP__
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#include <zest.hpp>
#include <memline.hpp>
#include <IndexedSet.hpp>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
class DedupCounts {
public:
    uint64_t total;
    uint64_t zero;
    uint64_t unique;
    uint64_t rc_tot;
    DedupCounts() {
        total  = 0ULL;
        zero   = 0ULL;
        unique = 0ULL;
        rc_tot = 0ULL;
    }
    void ResetNonUnique( void ) {
        total = 0ULL;
        zero  = 0ULL;
    }
};
class DedupCountByAlloc {
public:
    DedupCounts glob;
    DedupCounts kern;
    DedupCounts user;
    void ResetNonUnique( void ) {
        glob.ResetNonUnique();
        kern.ResetNonUnique();
        user.ResetNonUnique();
    }
    inline void IncrementTotal   ( const uint64_t globPageRC, const uint64_t kernPageRC, const uint64_t userPageRC  ) {
        glob.total += globPageRC;
        kern.total += kernPageRC;
        user.total += userPageRC;
    }
    inline void IncrementZero    ( const uint64_t globPageRC, const uint64_t kernPageRC, const uint64_t userPageRC  ) {
        glob.zero += globPageRC;
        kern.zero += kernPageRC;
        user.zero += userPageRC;
    }
    inline void IncrementUnique  ( const uint64_t kernPageRC, const uint64_t userPageRC  ) {
        glob.unique++;
        if( kernPageRC ) {
            kern.unique++;
        }
        if( userPageRC ) {
            user.unique++;
        }
    }
    inline void IncrementRCAccum ( const uint64_t globPageRC, const uint64_t kernPageRC, const uint64_t userPageRC  ) {
        glob.rc_tot += globPageRC;
        kern.rc_tot += kernPageRC;
        user.rc_tot += userPageRC;
    }
};
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#include <map>
#include <string>
#include <vector>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#include <Timer.hpp>
#include <DRAMImageStream.hpp>
#include <HashFunctions.hpp>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
class BaseDedupMaster;
class BaseDedupThread {
    const bool sync;            // disk i/o options
    pthread_mutex_t * disklock; // disk i/o options
    
    const uint32_t tidx;        // thread index

protected:
    // the raw data from the memory image
    line_t * line; // 64 bytes
    page_t * page; //  4 kB
    page_t * huge; //  2 MB
    
    // d-left hash tables to store unique instances
    // ... fg: fine-grain, 64 byte lines
    // ... pg: page-grain, 4kB pages
    // ... hg: huge-grain, 2MB pages
    DleftIndexedCounters * fg;
    DleftIndexedCounters * pg;
    DleftIndexedCounters * hg;

    // for the progress meter:
    static const float updateInterval = 10.0;
    float accumProgress;
    float nextProgress;

    // number of files in the memory image
    // ... typically it is split into 4GB files
    // ... so for 32GB of DRAM, numChunks is 8
    uint32_t numChunks;

    uint32_t kernPageRC; // 4kB page reference count, kernel & user memory
    uint32_t kernHugeRC; // 2MB page reference count, kernel & user memory
    int32_t  userPageRC; // 4kB page reference count, user memory
    int32_t  userHugeRC; // 2MB page reference count, user memory
    
    uint32_t lineIdx; // in range [ 0, linesPerPage-1 ]
    uint32_t hugeIdx; // in range [ 0, linesPerHuge-1 ]
    uint32_t passIdx; // in range [ 0, numPasses ]
    
    // points to a hash function in BaseDedupMaster
    HashWrapper * hf;

    DRAMImageStream imageStream; // wraps the memory image file descriptor
    RCImageStream   refctStream; // wraps the reference count file descriptor
    
    const std::vector< std::string > * img_files; // memory image file names
    const std::vector< std::string > * ref_files; // reference count file names

    // points to BaseDedupMaster
    // used for progress updates
    BaseDedupMaster * parent;

    // deduplicate lines, pages, or huge pages
    // ... unique instances are stored in the fg, pg, and hg dleft hash tables
    virtual void LineDedup( const uint64_t currPassIdx ) = 0;
    virtual void PageDedup( const uint64_t currPassIdx ) = 0;
    virtual void HugeDedup( const uint64_t currPassIdx ) = 0;
    
    // iterate over content in 1 particular chunk of the memory image
    void LoadMemImage( const char * img_file, const char * ref_file, const uint64_t passIdx );
    
    // open the memory image & reference count file
    // ... do some simple sanity checks
    void SanityOpenFiles( const char * mem_image_path, const char * ref_count_path );

    // update member variables user[Page|Huge]RC & kern[Page|Huge]RC
    inline void UpdateRefCounts( void ) {
        if( lineIdx == 0 ) {
            ReadPageRefCounts();
            if( hugeIdx == 0 ) {
                kernHugeRC = kernPageRC;
                userHugeRC = userPageRC;
            }
        }
    }
    inline void ReadPageRefCounts( void ) {
        refctStream.read_page_refs( &kernPageRC, &userPageRC );
        
        // for user page ref counts "-1" is no reference and "0" is one reference (why!?!)
        userPageRC++;
        
        // zest does not track virtual memory allocation (which can be much larger than physical)
        // so we reset these reference counts to one, i.e. because there is only one region of physical
        // memory that backs this page (logical reason...)
        // and the real reason to set these to one: because it is convenient as they are used later
        if( userPageRC ) { userPageRC = 1; }
        if( kernPageRC ) { kernPageRC = 1; }
    }

    void ProgressUpdate( const uint32_t currPassIdx );    
    void ResetProgress( void );
    void FinalizeProgress( void );
        
public:
    BaseDedupThread( BaseDedupMaster * _parent, const uint32_t _tidx, HashWrapper * _hf, pthread_mutex_t * _disklock, const bool _sync ) :
        sync      ( _sync ),
        disklock  ( _disklock ),
        tidx      ( _tidx ),
        hf        ( _hf ),
        parent    ( _parent )
    {
        lineIdx = 0;
        hugeIdx = 0;
        passIdx = 0;

        line = new line_t;
        page = new page_t( linesPerPage );
        huge = new page_t( linesPerHuge );
    }
    virtual ~BaseDedupThread( void ) {
        delete line;
        delete page;
        delete huge;
    }

    // counts of duplicate content
    // ... first broken into all memory, kernel memory, and user memory
    // ... then broken into total count, total non-zero count, unique count, zero valued count
    DedupCountByAlloc lineCounts;
    DedupCountByAlloc pageCounts;
    DedupCountByAlloc hugeCounts;

    // calls LoadMemImage() on each chunk of the memory image assigned to this thread
    void LoadMemImages( void );
    
    // assigns particular chunks (of the memory image) to this thread
    void SetFileVectorPtrs( const std::vector< std::string > * _img_files, const std::vector< std::string > * _ref_files );
};
class BaseDedupMaster {
    std::map< uint64_t, uint64_t > rchisto;

    void BuildFileNameVectors( const char * mem_image_path, const char * ref_count_path );
    
    // counts of duplicate content
    // ... first broken into all memory, kernel memory, and user memory
    // ... then broken into total count, total non-zero count, unique count, zero valued count
    DedupCountByAlloc lineCounts;
    DedupCountByAlloc pageCounts;
    DedupCountByAlloc hugeCounts;

    // accumulate counts from:
    // ... the d-left hash tables
    // ... and from the threads
    void AccumUnique( void );
    void AccumTotals( void );

    // individual stats printouts:
    // ... all of these are directly, or indirectly, invoked by PrintStats()
    void PrintHSep( void ) const;
    void PrintRCHisto( void ) const;
    void PrintHashTableStats( void ) const;
    void PrintDedupStatsKernel( const DedupCounts & lineCounts, const DedupCounts & pageCounts, const DedupCounts & hugeCounts, const char * title ) const;
    void PrintDedupStats( void ) const;
protected:
    static const bool verbose = true;
    
    DleftIndexedCounters * fg;
    DleftIndexedCounters * pg;
    DleftIndexedCounters * hg;
    
    pthread_mutex_t disklock;
    
    const uint64_t numPasses;
    const uint32_t numChunks;
    const uint32_t numThreads;
    const bool impl;
    
    static const uint32_t updateInterval = 10;
    uint32_t totalProgress;
    uint32_t nextProgress;
    uint64_t totalNumBytes;
    
    // list of memory image files & reference count files:
    std::vector< std::string > img_files;
    std::vector< std::string > ref_files;
    
    // pointers to the threads:
    std::vector< pthread_t * > pthreads;
    std::vector< BaseDedupThread * > bddthreads;
    
    // file name assignments by thread:
    // ... each thread has a pointer to these two vectors (of vectors)
    // ... memory image file names:     thread_img_files[ tidx ][ fidx ]
    // ... reference count file names:  thread_ref_files[ tidx ][ fidx ]
    // ... ... tidx in [ 0, numThreads-1 ]
    // ... ... fidx in [ 0, numChunks / numThreads - 1 ]
    std::vector< std::vector< std::string > > thread_img_files;
    std::vector< std::vector< std::string > > thread_ref_files;
    
    // hash function shared by children:
    JenkinsHashNonZero jhf;
    
    // timer for progress updates:
    Timer timer;
    
    // used to size the hash tables, invoked in Accu/FastDedup constructor:
    uint64_t SumMemImageChunkSizes( void ) const;
    
    void AccumCounts( void );   // accumulate dedup counts from threads & from hash table
    void BuildRCHisto( void );  // build histogram of reference counts form hash table
    
    // usually more chunks than threads, assign each chunk to a particular thread, round robin
    void DivideFilesByThreads( std::vector< BaseDedupThread * > & ddthreads );

    // print the dedup stats: this generates the 'main' report
    void PrintStats( void ) const;
public:
    BaseDedupMaster( const uint64_t _numPasses, const uint32_t _numChunks, const uint32_t _numThreads, const char * mipath, const char * rcpath, const bool _impl ) : numPasses( _numPasses ), numChunks( _numChunks ), numThreads( _numThreads ), impl( _impl ) {
        
        pthread_mutex_init( &disklock, NULL );
        
        for( uint32_t tidx = 0; tidx < numThreads; tidx++ ) {

            std::vector< std::string > ti;
            std::vector< std::string > tr;
            pthread_t * pt = new pthread_t;
            
            thread_img_files.push_back( ti );
            thread_ref_files.push_back( tr );
            pthreads.push_back( pt );
        }
        BuildFileNameVectors( mipath, rcpath );
    }
    virtual ~BaseDedupMaster( void ) {
        for( uint32_t tidx = 0; tidx < numThreads; tidx++ ) {
            delete pthreads[ tidx ];
        }
    }
    void ProgressMessage( const uint32_t currPassIdx );    
    inline void ProgressUpdate( const uint32_t progress, const uint32_t currPassIdx ) {

        const uint32_t currProgress = __sync_add_and_fetch( &totalProgress, progress );
                
        if( ( currProgress / numThreads ) >= nextProgress ) {
            ProgressMessage( currPassIdx );
        }
    }
    inline void ResetProgressMeter( void ) {
        totalProgress = 0;
        nextProgress  = updateInterval;
        timer.Reset();
        timer.Start();
    }
};
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#endif

